package personal.leil.learning.median;

import java.util.PriorityQueue;

/**
 * 给定一组数字，计算中位数
 *
 * @author Leil
 * @version 1.0
 * @since 2024/1/29
 */
public class MedianCalculate {

    /**
     * 计算一个数组的中位数
     * <p>
     *     <ol>
     *         <li>分别创建一个大根堆和一个小根堆</li>
     *         <li>将数组中的第一个数添加到大根堆中</li>
     *         <li>对数组中的每个数做如下操作：大于大根堆堆顶，入小根堆，反之，入大根堆</li>
     *         <li>经过以上操作后，计算大根堆和小根堆的size差，如果size超过1，则平衡两个堆的数据量</li>
     *         <li>计算数组的个数，如果是偶数个，则中位数是中间两个数字之和除以2</li>
     *         <li>如果是奇数个，则找size较大的堆弹出堆顶</li>
     *     </ol>
     * </p>
     *
     * @param arr target array
     * @return result for median calculate
     */
    public static double calc(int[] arr) {
        PriorityQueue<Integer> maxRootQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> minRootQueue = new PriorityQueue<>();
        maxRootQueue.offer(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            Integer rootForMax = maxRootQueue.peek();
            if ((rootForMax == null)) {
                return 0;
            }
            if (arr[i] > rootForMax) {
                minRootQueue.offer(arr[i]);
            } else {
                maxRootQueue.offer(arr[i]);
            }
            // balance for two queue
            int sizeGap = maxRootQueue.size() - minRootQueue.size();
            if (Math.abs(sizeGap) > 1) {
                if (sizeGap < 0) {
                    maxRootQueue.offer(minRootQueue.poll());
                } else {
                    minRootQueue.offer(maxRootQueue.poll());
                }
            }
        }
        int flag = arr.length % 2;
        if (flag == 0) {
            int a = maxRootQueue.peek() == null ? 0 : maxRootQueue.poll();
            int b = minRootQueue.peek() == null ? 1 : minRootQueue.poll();
            return (a + b) / 2.0;
        } else {
            return maxRootQueue.size() > minRootQueue.size() ?
                    maxRootQueue.poll() :
                    minRootQueue.peek() == null ? 0 : minRootQueue.poll();
        }
    }


    /*************************** For Test *********************************/
    public static void main(String[] args) {
        int[] arr = new int[]{23, 43, 5, 5, 56, 3, 5, 656, 49, 33};
        double result = calc(arr);
        System.out.println("Result for Median Calculate : " + result);
    }


}
